1307. Наибольшая грань

Гранью (border, verge, brink) br строки S называется любой собственный префикс этой строки, равный суффиксу S.

Строка S = abaababaabaab имеет две грани (не пустые) - ab и abaab. Строка S = abaabaab также имеет две грани – ab и abaab, но вторая грань – перекрывающаяся. Строка длины n из повторяющегося символа, например aaaaaaaa (или a⁸), имеет n – 1 грань. Для S = a⁸ это грани: a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa.

Понятие "собственный префикс" исключает грань, совпадающую с самой строкой.

Длина грани – это количество символов в ней.

Естественным обобщением понятия "грань" является понятие "наибольшей грани" – это наибольший (по количеству символов) собственный префикс строки, равный её суффиксу.

Вход. Дана строка S (|S| ≤ 10⁶).

Выход. Единственное число – длина наибольшей грани.

Пример входа	Пример выхода
abaabaab	5

РЕШЕНИЕ

строки – префикс-функция

Анализ алгоритма

Построим для строки S в массиве p префикс-функцию. Если длина строки S равна n, то для решения задачи достаточно вывести значение p[n – 1].

Реализация алгоритма

Входная строка s содержит не более MAX = 1000010 символов. Префикс-функцию строим в массиве p.

#define MAX 1000010

char s[MAX];

int p[MAX];

Строим префикс-функцию для строки s длины n при помощи функции MaxBorderArray. Выводим длину наибольшей грани строки, которая находится в p[n – 1].

gets(s); n = strlen(s);

MaxBorderArray();

printf("%d\n",p[n-1]);